/**
 * @brief 树堆的实现
 */
template <typename T>
class TreeHeap {
public:
    struct Node {
        T value;
        std::shared_ptr<Node> left;
        std::shared_ptr<Node> right;
        std::shared_ptr<Node> parent;

        Node(const T& val) : value(val), left(nullptr), right(nullptr), parent(nullptr) {}
    };

    TreeHeap() : root(nullptr) {}

    bool empty() const {
        return !root;
    }

    void insert(const T& val) {
        auto node = std::make_shared<Node>(val);
        root = merge(root, node);
    }

    void erase(const T& val) {
        auto node = find(root, val);
        if (node) {
            root = merge(node->left, node->right);
            if (root) {
                root->parent = nullptr;
            }
        }
    }

    T get_min() const {
        if (!root) {
            throw std::logic_error("Heap is empty");
        }
        return root->value;
    }

    void merge(TreeHeap& other) {
        root = merge(root, other.root);
        other.root = nullptr;
    }

private:
    std::shared_ptr<Node> root;

    std::shared_ptr<Node> merge(std::shared_ptr<Node> a, std::shared_ptr<Node> b) {
        if (!a) {
            return b;
        }
        if (!b) {
            return a;
        }
        if (b->value < a->value) {
            std::swap(a, b);
        }
        if (!a->left) {
            a->left = b;
            b->parent = a;
        } else {
            a->right = merge(a->right, b);
            a->right->parent = a;
            if (a->right->value < a->left->value) {
                std::swap(a->left, a->right);
            }
        }
        return a;
    }

    std::shared_ptr<Node> find(std::shared_ptr<Node> node, const T& val) const {
        if (!node) {
            return nullptr;
        }
        if (node->value == val) {
            return node;
        }
        auto left = find(node->left, val);
        if (left) {
            return left;
        }
        return find(node->right, val);
    }
};
